package com.sicheng.lc.周赛.分类.并差集;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/20 22:59
 */
public class 慧眼神瞳 {
    //https://leetcode.cn/contest/sf-tech/problems/BN8jAm/
    int count;
    int[] p;


    public boolean isCompliance(int[][] distance, int n) {
        init(distance.length);
        for (int i = 0; i < distance.length - 1; i++) {
            for (int j = i + 1; j < distance[0].length; j++) {
                if (distance[i][j] <= 2) {
                    union(i, j);
                }
            }
        }
        return n >= count;
    }

    int find(int x) {
        if (x == p[x])
            return x;

        return p[x] = find(p[x]);
    }

    void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) {
            p[pb] = pa;
            count--;
        }
    }

    private void init(int n) {
        count = n;
        p = new int[n];
        for (int i = 0; i < p.length; i++) {
            p[i] = i;
        }
    }

    public static void main(String[] args) {
        慧眼神瞳 solution = new 慧眼神瞳();
        int[][] d = {
                {0, 4, 3, 2, 4, 4, 2, 3, 4, 4},
                {4, 0, 5, 1, 4, 4, 2, 4, 5, 6},
                {3, 5, 0, 3, 3, 3, 1, 6, 4, 3},
                {2, 1, 3, 0, 3, 6, 3, 3, 1, 4},
                {4, 4, 3, 3, 0, 3, 3, 1, 4, 4},
                {4, 4, 3, 6, 3, 0, 4, 7, 5, 6},
                {2, 2, 1, 3, 3, 4, 0, 5, 4, 4},
                {3, 4, 6, 3, 1, 7, 5, 0, 4, 3},
                {4, 5, 4, 1, 4, 5, 4, 4, 0, 5},
                {4, 6, 3, 4, 4, 6, 4, 3, 5, 0}
        };
        System.out.println(solution.isCompliance(d, 3));
    }
}
